#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <iostream>
using namespace std;
//现有两个有序的数组A和数组B，而且数组A后面的空间足以容纳A和B
//要求将数组B中所有元素都插入到数组A中，并且保证所有的数字都是有序的

void MergeTwoSortArray(int *array_A,size_t len_A,size_t capacity,int *array_B,size_t len_B)
{
    assert(array_A);
    assert(len_A>0);
    if(NULL==array_B||len_B<=0||capacity<(len_A+len_B))
        return;
    size_t cur_a=len_A-1;
    size_t cur_b=len_B-1;
    size_t end=capacity-1;
    while((int)cur_b>=0&&(int)cur_a>=0)
    {
        if(array_B[cur_b]>array_A[cur_a])
        {
            array_A[end--]=array_B[cur_b--];
        }
        else
        {
            array_A[end--]=array_A[cur_a--];
        }
    }
    while((int)cur_b>=0)
    {
        array_A[end--]=array_B[cur_b--];
    }
    //这里只处理当B中的元素没有遍历完的情况，需要将其剩下的都搬到A中来
    //因为如果B中遍历完了，A中没有遍历完仍然是在数组A中
}
void Print(int *array,size_t len,const char *msg)
{
    if(NULL==array||len<=0)
    {
        return;
    }
    puts(msg);
    size_t i=0;
    for(i=0;i<len;i++)
    {
        printf("[%d] ",array[i]);
    }
    printf("\n");
}
void TestMergeTwoSortArray()
{
    //int array_1[]={1,7,9,12,34,56,100,234};
    //int array_B[]={2,3,4,5,6,23,34,56,98,256,1013};
    //int array_1[]={1,7,9,12,34,56,100,234};
    //int array_B[]={-3,-2,-1};
    int array_1[]={-3,-2,-1};
    int array_B[]={4,5,8,9};
    size_t len_1=sizeof(array_1)/sizeof(*array_1);
    size_t len_B=sizeof(array_B)/sizeof(*array_B);
    size_t capacity=len_1+len_B;
    size_t len_A=len_1;
    int *array_A=new int[capacity];
    //这里需要自己来保证数组array_A 的大小足以容纳array_A和array_B
    memcpy(array_A,array_1,sizeof(int)*len_1);
    Print(array_A,capacity,"数组A");
    Print(array_B,len_B,"数组B");
    MergeTwoSortArray(array_A,len_A,capacity,array_B,len_B);
    Print(array_A,capacity,"合并之后");
    delete [] array_A;
}
int main()
{
    TestMergeTwoSortArray();
    return 0;
}

